package advance.day01;

import base.day05.Node;

/**
 * 描述：
 *    t2是否为t1的某颗子树
 * @author hl
 * @version 1.0
 * @date 2020/11/4 16:31
 */
public class T1SubtreeEqualsT2 {
//    static class Node{
//        String value;
//        Node left;
//        Node right;
//
//        public Node(String value) {
//            this.value = value;
//        }
//    }
    public static boolean isSubtree(Node t1, Node t2){
        String str1 = serialByPre(t1);
        String str2 = serialByPre(t2);
        return getIndexOf(str1, str2) != -1;
    }

    private static int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        int[] next = getNextArr(m);
        int p1 = 0;
        int p2 = 0;
        while(p1 < s.length() && p2 < m.length()){
            if (s.charAt(p1) == m.charAt(p2)) {
                p1++;
                p2++;
            }else if (next[p2] > 0) {
                p2 = next[p2];
            }else{
                p1++;
            }
        }
        return p2 == m.length() ? p1 - p2 : -1;
    }

    private static int[] getNextArr(String m) {
        int[] next = new int[m.length()];
        next[0] = -1;
        next[1] = 0;
        int cn = 0;
        int index = 2;
        while(index < m.length()){
            if (m.charAt(index - 1) == m.charAt(cn)) {
                next[index++] = ++cn;
            }else if (cn > 0) {
                cn = next[cn];
            }else{
                next[index++] = 0;
            }
        }
        return next;
    }

    public static String serialByPre(Node head){
        if (head == null) {
            return "#!";
        }
        String res = head.value + "#";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }
    public static void main(String[] args) {
        Node t1 = new Node(1);
        t1.left = new Node(2);
        t1.right = new Node(3);
        t1.left.left = new Node(4);
        t1.left.right = new Node(5);
        t1.right.left = new Node(6);
        t1.right.right = new Node(7);
        t1.left.left.right = new Node(8);
        t1.left.right.left = new Node(9);

        Node t2 = new Node(2);
        t2.left = new Node(4);
        t2.left.right = new Node(8);
        t2.right = new Node(5);
        t2.right.left = new Node(9);

        System.out.println(isSubtree(t1, t2));

    }
}
